// 换根
// https://www.luogu.com.cn/problem/P1364

int n;
vector<int> adj[maxn];
int f[maxn], siz[maxn]; // f[u] 表示 u 的所有子节点到 u 的距离之和
int ans[maxn];          // ans[u] 表示所有节点到 u 的距离之和
// f[u] = sum(w_{u,v} * siz_v + f[v])
// ans[v] = ans[u] - w_{u, v} * siz_v + w_{u,v} * (n - siz_v)

int init(int now = 1, int fa = 0, int dep = 0) {
    f[1] += a[now] * dep;
    int cnt = a[now];
    for (auto &p : adj[now])
        if (p != fa)
            cnt += init(p, now, dep + 1);
    return siz[now] = cnt;
}

void dfs(int now = 1, int fa = 0) {
    ans = min(ans, f[now]);
    for (auto &p : adj[now])
        if (p != fa)
            f[p] = f[now] + siz[1] - siz[p] - siz[p], dfs(p, now);
}
